#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution1
{
public:
    int prc(int x)
    {
        int sum = 0;
        while (x!= 0)
        {
            sum += (x % 10) * (x % 10);
            x /= 10;
        }
        return sum;
    }
    bool isHappy(int n)
    {
        int slow = prc(n), fast = prc(prc(n));
        while (slow != fast)
        {
            slow = prc(slow);
            fast = prc(prc(fast));
        }
        if (slow == 1) return true;
        else return false;
    }
};
class Solution2
{
public:
    int maxArea(vector<int>& height)
    {
        int pre = 0, tail = height.size() - 1;
        int Max = 0;
        while (pre != tail)
        {
            int s = (tail - pre) * min(height[pre], height[tail]);
            Max = max(Max,s);
            if (height[pre] > height[tail]) tail--;
            else pre++;
        }
        return Max;
    }
};
class Solution3
{
public:
    int triangleNumber(vector<int>& nums)
    {
        int cnt = 0;
        int n = nums.size() - 1;
        sort(nums.begin(), nums.end());
        while (n >= 2)
        {
            int index_a = 0, index_b = n - 1;
            int c = nums[n], a = nums[index_a], b = nums[index_b];
            while (index_a != index_b)
            {
                a = nums[index_a];
                b = nums[index_b];
                if ((a+b) > c)
                {
                    cnt += index_b - index_a;
                    index_b--;
                }
                else
                {
                    index_a++;
                }
            }
            n--;
        }
        return cnt;
    }
};
//class Solution
//{
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        vector<vector<int>> vv;
//        int k = nums.size() - 1;
//        while (k>=2)
//        {
//            int i = 0, j = k - 1;
//            while (i < j)
//            {
//                if (nums[i] + nums[j] + nums[k] == 0)
//                    vv.push_back({ nums[i],nums[j],nums[k] });
//                while (i < k&&nums[i] == nums[i + 1])
//                    i++;
//                while (j > 0&&nums[j] == nums[j - 1] )
//                    j--;
//                if (i < k) i++;
//                if (j > 0) j--;
//            }
//            k--;
//        }
//        return vv;
//    }
//};
class Solution7
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int k = nums.size() - 1;
        while (k >= 2)
        {
            if (nums[k] == 1)
            {
                int a = 0;
            }
            int i = 0, j = k - 1;
            while (i < j)
            {
                if (nums[i] + nums[j] + nums[k] == 0)
                    vv.push_back({ nums[i],nums[j],nums[k] });
                if (nums[i] + nums[j] > -nums[k])
                {
                    while (j > 0 && nums[j] == nums[j - 1])
                        j--;
                    j--;
                }
                else if (nums[i] + nums[j] < -nums[k])
                {
                    while (i < k && nums[i] == nums[i + 1])
                        i++;
                    i++;
                }
                else
                {
                    while (j > 0 && nums[j] == nums[j - 1])
                        j--;
                    while (i < k && nums[i] == nums[i + 1])
                        i++;
                    i++;j--;
                }
            }
            while (k >= 2 && nums[k] == nums[k - 1]) k--;
            k--;
        }
        return vv;
    }
};
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> vv;
        sort(nums.begin(), nums.end());
        int d = nums.size() - 1;
        while (d >= 3)
        {
            int c = d - 1;
            while (c >= 2)
            {
                int a = 0, b = c - 1;
                while (a < b)
                {
                    if (nums[a] + nums[b] > target - nums[c] - nums[d])
                        b--;
                    else if (nums[a] + nums[b] < target - nums[c] - nums[d])
                        a++;
                    else if (nums[a] + nums[b] == target - nums[c] - nums[d])
                    {
                        vv.push_back({ nums[a],nums[b],nums[c],nums[d] });
                        a++;b--;
                        while (a < c && nums[a] == nums[a - 1]) a++;
                        while (b > 0 && nums[b] == nums[b + 1]) b--;
                    }
                }
                c--;
                while (c > 2 && nums[c] == nums[c + 1]) c--;
            }
            d--;
            while (d > 3 && nums[d] == nums[d + 1]) d--;
        }
        return vv;
    }
};
int main()
{
    vector<int> v = { 2,2,2,2,2};
    Solution().fourSum(v,8);
	return 0;
}